#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include "/home/sravani/bst/bst.h"

bst_node *root = NULL;
//This function allocates the memory to the new bst_node
bst_node *getmemory()
{
	bst_node *new_node;
	new_node = (bst_node *)malloc(sizeof(bst_node));
	if(new_node == NULL)	//If system runs out of memory
	{
		printf("Insufficient Memory\n");
		exit(0);
	}
	return new_node;
}
void insertNewNode(f_desc *fd_ins_data)
{	
	bst_node *new_node,*temp,*temp1;
	new_node=getmemory();
	new_node->left=NULL;
	new_node->right=NULL;
	new_node->parent=NULL;
	new_node->fd_data=(f_desc *)malloc(sizeof(f_desc));
	if(new_node->fd_data == NULL)	//If system runs out of memory
	{
		printf("Insufficient Memory\n");
		exit(0);
	}
	new_node->fd_data=fd_ins_data;
	printf("loc number :%ld",(new_node->fd_data)->locBlockNo);
	if(root == NULL){
		root = new_node;
        	printf ("root %s \n", (new_node->fd_data)->path);
   	}
	else
	{
		//compare path with each node data and move either to left or right child
		temp = root;
		temp1 = NULL;
		while(temp!=NULL)
		{
			if(strcmp((new_node->fd_data)->path,(temp->fd_data)->path) == 0)
			{
               			printf("Path already exists in BST Node");
           		}
           		else
			{
                		if(strcmp((new_node->fd_data)->path,(temp->fd_data)->path) < 0)
				{
                    			temp1 = temp;
                    			temp = temp->left;
                		}
               			else
				{
                    			temp1 = temp;
                    			temp = temp->right;
                		}
            		}
        	}
        	new_node->parent = temp1;
		if(strcmp((new_node->fd_data)->path,(temp1->fd_data)->path) < 0)
		{
		    temp1->left =new_node;
		    printf(" left %s \n",(new_node->fd_data)->path);
		}
		else
		{
		    temp1->right = new_node;
		    printf(" right %s \n",(new_node->fd_data)->path);
		}   
    	}
}
void inorderTraversal(bst_node *bst_root)
{
	bst_node *temp;
	temp=bst_root;
	if(temp)
	{
		inorderTraversal(temp->left);
		printf("%s\n",(temp->fd_data)->path);
		inorderTraversal(temp->right);
	}
}
void displayBST(bst_node *bst_root)
{
	if(bst_root == NULL)
		printf("Empty tree");
	else
		inorderTraversal(bst_root);
}
bst_node* searchBST(bst_node *root,char *data)
{
	if(root == NULL || (strcmp(data,(root->fd_data)->path) ==0))
	{
	        return root;
   	}
    	else
    	{
		if( strcmp( data,(root->fd_data)->path) <0 )
		{
        		return searchBST(root->left,data);
        	}
        	else
        	{
        		return searchBST(root->right,data);
        	}
    	}
}

void transplantBST(bst_node *delNode,bst_node *delNodeChild)
{
	if(delNode->parent == NULL)
	{
	        root = delNodeChild;
	}
	else
	{
		if(delNode == delNode->parent->left)
		{
		    delNode->parent->left = delNodeChild;
		}
		else
		{
		    delNode->parent->right = delNodeChild;
		}
		if(delNodeChild != NULL)
		{
		    delNodeChild->parent = delNode->parent;
		}
	}
}
bst_node * treeMinimum(bst_node *min)
{
    while(min->left != NULL){
        min = min->left;
    }
    printf("%s",(min->fd_data)->path);
    return min;
}
void deleteNode(bst_node *root,char *data)
{
	bst_node *location;
    	bst_node *temp = root;
    	bst_node *min=NULL;
	location = searchBST(root,data);
    	if(location != NULL)
	{
        	printf("element is present\n");
	        if(location->left == NULL)
		{
            		transplantBST(location,location->right);
        	}
		else
		{
		        if(location->right==NULL)
			{
		        	transplantBST(location,location->left);
		        }
		        else
			{
		        	min = treeMinimum(location->right);
		        	if(min->parent != location)
				{
			                transplantBST(min,min->right);
			                min->right = location->right;
			                min->right->parent = min;
				}
		        	transplantBST(location,min);
		            	min->left = location->left;
		            	min->left->parent = min;
		            	min->parent = location->parent;
		        }
		}
        	free(location);
    }
    else
    {
        printf("element is not present\n");
    }
}
main()
{
	int choice,c,i,flag;
	bst_node *location;
	f_desc *data,*data2,*data3;
	data= (f_desc *)malloc(sizeof(f_desc));
	strcpy(data->fName,"lmn");
	strcpy(data->path,"home/sravvani/lmn.txt");
	strcpy(data->ftype,"text");
	data->locBlockNo=1000;
	insertNewNode(data);
	data2= (f_desc *)malloc(sizeof(f_desc));
	strcpy(data2->fName,"abc");
	strcpy(data2->path,"home/sravvani/abc.txt");
	strcpy(data2->ftype,"text");
	data2->locBlockNo=2000;
	insertNewNode(data2);
	data3= (f_desc *)malloc(sizeof(f_desc));
	strcpy(data3->fName,"def");
	strcpy(data3->path,"home/sravvani/def.txt");
	strcpy(data3->ftype,"text");
	data3->locBlockNo=3000;
	insertNewNode(data3);
	printf("\ndisplaying elements of BST now..........\n");
	displayBST(root);
	printf("\nelement to search is home/sravvani/abc.txt\n");
    	char data1[]= "home/sravvani/abc.txt";   
    	location = searchBST(root,data1);
    	if(location != NULL)
	{
       		printf("element is present\n");
		printf("location number %ld\n",(location->fd_data)->locBlockNo);
    	}
    	else
    	{
       		printf("element is not present\n");
    	}
	printf("\nenter an element to delete:abc\n");
	char data4[]= "home/sravvani/abc.txt";   
	deleteNode(root,data4);
	printf("element deleted\n");
	printf("\nelements in BST\n");
	displayBST(root);
}
